package sword.chapter8Tree;

import java.util.HashSet;
import java.util.Stack;

/**
 * 二叉搜索树中两个结点之和
 *
 * O(h) 双指针 中序遍历 反向中序遍历
 * O(n) HashSet 中序遍历
 *
 * @author K
 * @date 2021/12/13 14:30
 */
public class S56FindTarget {

    /**
     * 使用HashSet记录了历史值
     * 时间复杂度O(n)
     * 空间复杂度O(1)
     */
    public static boolean s56(TreeNode root, int target) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        // key：节点值
        HashSet<Integer> set = new HashSet<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if (set.contains(target - cur.val)) {
                return true;
            }
            set.add(cur.val);
            cur = cur.right;
        }
        return false;
    }

    /**
     * 双指针
     * O(h)
     */
    public static boolean s56A(TreeNode root, int target) {
        BSTIterator iterator = new BSTIterator(root);
        BSTIteratorReversed iteratorReversed = new BSTIteratorReversed(root);
        int next = iterator.next();
        int prev = iteratorReversed.prev();
        while (next != prev) {
            if (next + prev == target) {
                return true;
            }
            if (next + prev > target) {
                prev = iteratorReversed.prev();
            } else {
                next = iterator.next();
            }
        }
        return false;
    }



    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        TreeNode node2 = new TreeNode(2);
        TreeNode node5 = new TreeNode(5);
        TreeNode node1 = new TreeNode(1);
        TreeNode node3 = new TreeNode(3);
        TreeNode node6 = new TreeNode(6);
        root.left = node2;
        root.right = node5;
        node2.left = node1;
        node2.right = node3;
        node5.right = node6;

        boolean result = s56(root, 6);
        boolean result2 = s56A(root, 6);
        System.out.println();
    }
}

/**
 * 中序遍历 正向（从小到大）
 */
class BSTIterator {
    TreeNode cur;
    Stack<TreeNode> stack;

    BSTIterator(TreeNode root) {
        cur = root;
        stack = new Stack<>();
    }

    public boolean hasNext() {
        return cur != null || !stack.isEmpty();
    }

    public int next() {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        int result = cur.val;
        cur = cur.right;
        return result;
    }
}

/**
 * 中序遍历 反向（从大到小）
 */
class BSTIteratorReversed {
    TreeNode prev;
    Stack<TreeNode> stack;

    BSTIteratorReversed(TreeNode root) {
        prev = root;
        stack = new Stack<>();
    }

    public boolean hasNext() {
        return prev != null || !stack.isEmpty();
    }

    public int prev() {
        while (prev != null) {
            stack.push(prev);
            prev = prev.right;
        }
        prev = stack.pop();
        int result = prev.val;
        prev = prev.left;
        return result;
    }
}